#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//图的存储结构
//邻接矩阵表示法 
#define MaxVertexNum 5 //顶点数目的最大值
typedef struct{
	int Vertex[MaxVertexNum];//顶点 
	int Edge[MaxVertexNum][MaxVertexNum];//边的权 ，或者无权图0/1 
	int vexnum,arcnum;//图的当前顶点数和弧数 
}MGraph;
//采用DFS算法实现逆拓扑排序
//AOV网是有向无环图 
//要判断是否有环
//全局变量 
bool  visited[MaxVertexNum];//访问标记数组，初始都为false，全局变量
bool isPointed[MaxVertexNum];//初始都为false，用于记录当前结点是否被指向
bool flag=0;//用来标记是否出现了回路
int count=0;//用来记录已经输出的顶点个数
int print[MaxVertexNum];//保存要输出的顶点 

int FirstNeighbor(MGraph G,int v);//返回图G中顶点V的第一个邻接点，若有则返回该邻接点的序号，否则返回-1
int NextNeighbor(MGraph G,int v,int w);//返回图G中顶点v在顶点w之后的下一个邻接点，若有则返回该邻接点序号，否则返回-1 
void DFS(MGraph G,int v);

void DFSTraverse(MGraph G){//对图G进行深度优先遍历 
    int i;
    for(i=0;i<G.vexnum;i++){
    	visited[i]=false;//初始化已访问标记数据 
    	isPointed[i]=false;
	} 
	for(i=0;i<G.vexnum;i++){
		if(!visited[i])
		DFS(G,i);
	}
	if(flag==1){
		printf("有回路，输出逆拓扑排序失败\n");
	}
	else{
	    printf("逆拓扑排序为:\n");
		for(i=0;i<G.vexnum;i++){
	    	printf("%d\n",print[i]);//打印逆逆拓扑排序 
		} 
	}
}
void DFS(MGraph G,int v){//从顶点v出发，深度优先遍历图G 
	if(flag==1) return;//说明有回路，逐层返回 
	visited[v]=true;//设已访问标志 
	isPointed[v]=false;//将结点v当做祖先结点 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ 
	   isPointed[w]=true;//将v指向的结点w的isPointed[]都设置为ture 
	   if(!visited[w]) DFS(G,w);//w为v的尚未访问的邻接顶点 
    }
    if(isPointed[v]==true) flag=1;//说明出现了回路 
    print[count++]=v;//将该顶点加入打印数组中 
}
//int FirstNeighbr(MGraph G,int v);返回图G中顶点V的第一个邻接点，若有则返回该邻接点的序号，否则返回-1
int FirstNeighbor(MGraph G,int v){
	for(int i=0;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
//int NextNeighbor(MGraph G,int v,int w);返回图G中顶点v在顶点w之后的下一个邻接点，若有则返回该邻接点序号，否则返回-1 
int NextNeighbor(MGraph G,int v,int w){
	for(int i=w+1;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
int main(){
	MGraph G;
	int i,j;
	for(i=0;i<MaxVertexNum;i++){
		for(j=0;j<MaxVertexNum;j++){
		   G.Edge[i][j]=0;
		}   
	}
	G.arcnum=5;
	G.vexnum=5;
	G.Edge[0][1]=1;
	G.Edge[0][3]=1;
	G.Edge[1][3]=1;
	G.Edge[2][1]=1;
	G.Edge[3][2]=1;
	G.Edge[4][3]=1;
	G.Edge[4][2]=1;
	DFSTraverse(G); 
	return 0;
}
/*
如果没有回路，那么每一轮递归只会沿着路径做最深访问，不会出现重复(从系统栈的角度，指向了还在栈中的节点)。
比如第一张图的0、1、3、4没有出现重复访问，但第二张图中，0、1、3、4、2、3，在同一轮递归中访问了重复的节点3。说明出现了回路（走了回头路）

因此我们可以添加一个数组nowVisited[]，记录每一轮递归节点被访问的情况。这样就有两个数组记录节点访问情况，visited[]记录全局访问情况，nowVisited[]只记录本轮递归的访问情况。
如果一个节点在本轮递归中没有访问，说明没有出现回路，继续执行代码。
如果一个节点在本轮递归被访问过了，说明出现了回路，代码立即中止执行。
*/